public class Sort2 {
    // 插入排序
    public static void insertSort(int[] array){
        for(int i=0;i<array.length;i++){
            int tmp=array[i];
            int j=i;
            while(j>0 && array[j-1]>tmp){
                array[j]=array[j-1];
                j--;
            }
            array[j]=tmp;
        }
    }
    // 希尔排序
    public static void shellSort(int[] array){
     for(int gap=array.length/2;gap>=1;gap/=2){
         for(int i=gap;i<array.length;i++){
             int tmp=array[i];
             int j=i-gap;
             while(j>=0 && array[j]>tmp){
                 array[j+gap]=array[j];
                 j-=gap;
             }
             array[j+gap]=tmp;
         }
         }
     }
    // 选择排序
    public static void selectSort(int[] array){
        for(int i=0;i<array.length;i++){
            int min=i;
            for(int j=i;j<array.length;j++){
                if(array[j]<array[min]) min=j;
            }
            int tmp=array[i];
            array[i]=array[min];
            array[min]=tmp;
        }
    }


    // 堆排序
    public static void heapSort(int[] array){
        int size=array.length;
        int root=(array.length-2)/2;
        for(;root>=0;root--){
            shiftDown(array,root,size);
        }
        for(int i=size-1;i>=1;i--){
            int tmp=array[i];
            array[i]=array[0];
            array[0]=tmp;
            size--;
            shiftDown(array,0,size);
        }
    }

    private static void shiftDown(int[] elem,int root,int len) {
        int parent=root;
        int child=root*2+1;
        while(child<len){
            if(child+1<len && elem[child+1]>elem[child]){
                child=child+1;
            }
            if(elem[parent]<elem[child]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
            }else{
                break;
            }
            parent=child;
            child=2*parent+1;
        }
    }
    // 冒泡排序
    public static void bubbleSort(int[] array){
        for(int i=1;i<array.length;i++){
            boolean flag=false;
            for(int j=0;j<array.length-i;j++){
                if(array[j+1]<array[j]){
                    int tmp=array[j+1];
                    array[j+1]=array[j];
                    array[j]=tmp;
                    flag=true;
                }
            }
            if(!flag) break;
        }
    }

    // 快速排序
    private static void swap(int[] array, int left, int right) {
        int tmp=array[left];
        array[left]=array[right];
        array[right]=tmp;
    }
    //Hare法
    private static int partitionHare(int[] array, int left, int right) {
        int i=left;
        int j=right;
        int provit=array[left];
        while(i<j){
            while(i<j && array[j]>=provit){
                j--;
            }
            while(i<j && array[i]<=provit){
                i++;
            }
            swap(array,i,j);
        }
        swap(array,left,i);
        return i;
    }
    //指针法
    private static int partition(int[] array, int left, int right) {
    int prev=left;
    int provit=array[left];
    int cur=prev+1;
    while(cur<=right){
        if(array[cur]<provit && array[prev]!=array[cur]){
            prev++;
            swap(array,cur,prev);
        }
        cur++;
    }
        swap(array,prev,left);
        return prev;
    }
    //挖坑法
    private static int partitionhole(int[] array, int left, int right) {
        int i=left;
        int j=right;
        int provit=array[left];
        while(i<j){
            while(i<j && array[j]>=provit){
                j--;
            }
            array[i]=array[j];
            while(i<j && array[i]<=provit){
                i++;
            }
            array[j]=array[i];
        }
        array[i]=provit;
        return i;
    }
    //递归左右子树
    public static void quickSort(int[] array,int left,int right){
      if(left>=right) return;
      int partition=partition(array,left,right);
      quickSort(array,left,partition-1);
      quickSort(array,partition+1,right);
    }
    public static void quickSort(int[] array){
        quickSort(array,0,array.length-1);
    }
}
